/*
 * DirectlyAddressedSet.h
 *
 *  Created on: 30/08/2012
 *      Author: marcio
 */

#ifndef DRIECTLYADDRESSEDSET_H_
#define DRIECTLYADDRESSEDSET_H_

#include <cstdlib>
#include <Factory.h>

/*!
 * \class DirectlyAddressedSet
 * \brief A static or dynamic set of elements with direct addressing.
 *
 * This abstract class represents a set of elements,
 * named *keys*, taken from a totally ordered universe \f$U = \{ 0, 1, \ldots, u - 1 \}\f$ of size \f$u \geq 0\f$.
 * Each key in the set is aimed at acting as a direct address in such a way that lookup, insert and delete operations can be
 * performed in constant time.
 * A class extending this abstract class must implement the actual data structure used to store this set.
 *
 * By definition, every key of the universe is either in this set or in its complement.
 * The complement is composed by the keys of the universe not in the set.
 * This class provide methods to query or manipulate the set and its complement with respect to the universe.
 * However, from a performance standpoint, it is often highly recommended that all or
 * some these methods be overriden in the concrete classes that extend from this one. In many cases, the general implementations
 * in this class will perform costly accesses to the set.
 *
 *
 */
class DirectlyAddressedSet {

public:
	/*! \class DirectlyAddressedSet::Iterator
	 * \brief A general iterator to scan a DirectlyAddressedSet.
	 *
	 * It scans each key in a set, allowing the programmer to traverse the set in either ascending or descending order.
	 * An object of this class has no current key; its cursor position always lies before the key that would be returned by a call
	 * to next(). An iterator for a set of size \f$n\f$ has \f$n+1\f$
	 * possible cursor positions, as illustrated by the indices below:
	 *
	 *                          Element(0)   Element(1)   Element(2)   ... Element(n-1)
	 *     cursor positions:  0            1            2           ...                  n
	 *
	 * An object of this class is backed by the corresponding set.
	 *
	 * An object of this class keeps the state of an enumeration. This means that
	 * various enumerations can be performed simultaneously provided that each of
	 * them is associated with a different iterator. However, an error may occur
	 * in a method of this class if the set is modified during the enumeration.
	 *
	 */
	class Iterator {
	protected:
		Iterator() {};
	public:

		/*!
		 * \brief The destructor.
		 *
		 * A simple destructor.
		 */
		virtual ~Iterator() {};

		/*!
		 * \brief Restarts the enumeration.
		 *
		 * The current state of the object will be lost and the cursor is reset to a position such that a call to next() returns
		 * the first key in the set. In special, the enumeration must be restarted when nextUpTo() fails.
		 *
		 * It is implemented in this class as restartFrom(0).
		 *
		 */
		virtual void restart();

		/*!
		 * \brief Restarts the enumeration from a specified value (which is not required to be a key in the universe).
		 *
		 * The current state of the object will be lost and the cursor is reset to the position such that a call to next() returns
		 * the smallest key greater than or equal to the specified value. In special, the enumeration must be restarted when nextUpTo()
		 * fails.
		 *
		 * \param from the specified value
		 */
		virtual void restartFrom(long from) = 0;

		/*!
		 * \brief Enumerates the first key in the set next to the current cursor position.
		 *
		 * This method may be called repeatedly to traverse the set in ascending order.
		 *
		 * An arbitrary value outside the universe is returned if there is no next key in the current set.
		 *
		 * \return the next element to be enumerated, if there is one, or a value greater than all values in the universe otherwise
		 */
		virtual long next() = 0;

		/*!
		 * \brief Enumerates the first key in the set next to the current cursor position up to a specified value.
		 *
		 * This method may be called repeatedly to traverse the set in ascending order. In special, this method is
		 * useful to enumerate a particular node of a level of a tree of bitmaps.
		 *
		 * This method differs from next() in the sense it stops searching for the next key when the specified limit is reached.
		 * If there is no next key in the current set up to the specified value, then the new cursor position is unpredictable and
		 * an arbitrary value greater than or equal to the specified range is returned. In this case, a call to restart() or restartFrom(long) must be
		 * performed before
		 * any call to enumeration methods.
		 *
		 * \param to the value to limit the enumeration
		 *
		 * \return the next key to be enumerated up to the specified value, if there is one, or a value greater than
		 * or equal to the specified value otherwise
		 */
		virtual long nextUpTo(long to) = 0;
	};

protected:

	const long 	u;			//!< the size of the universe

	static char *		bitvector;	//!< to be returned by toArray()
	static int			nbv;		//!< size of vEBTree<T>::bitvector, in number of bytes
	Iterator * const	setIt;		//!< internal iterator used to implement stateless enumeration methods on this set
	Iterator * const	complIt;	//!< internal iterator used to implement stateless enumeration methods on the complement of this set

	/*!
	 * \brief Basic constructor.
	 *
	 * A simple constructor to an empty set with a universe of a specified size.
	 *
	 * \param size of the universe.
	 *
	 **/
	DirectlyAddressedSet(long size);

public:

	/*!
	 * \brief Destructor
	 *
	 * A simple destructor to an object of this class
	 */
	virtual ~DirectlyAddressedSet();

	/*!
	 * \brief Creates a copy of this object.
	 *
	 * \return a copy of this object.
	 */
	virtual DirectlyAddressedSet * clone() const = 0;

	/*!
	 * \brief Starts a new iterator for this set.
	 *
	 * Returns an iterator to enumerate all the keys belonging to this object.
	 *
	 * The state of the returned iterator is reset to the beginning of the enumeration.
	 *
	 * \return the new iterator to the set
	 */
	virtual DirectlyAddressedSet::Iterator* newIterator() = 0;

	/*!
	 * \brief An Iterator for the complement of the set represented by the object
	 *
	 * Return an iterator to enumerate all the elements of the universe not belonging to
	 * this object
	 *
	 *
	 * \return an iterator to the complement of the set
	 */
	virtual DirectlyAddressedSet::Iterator* newComplIterator() = 0;

	/*!
	 * \brief Determines the next key in the set, in ascending order, of the specified value.
	 *
	 * This method returns the smallest key in the set which is greater than or equal to the specified value (which is not
	 * required to be a key in the universe). An arbitrary value is returned if there is no next key in the set.
	 *
	 * This method is provided by convenience, but it is less efficient than using an iterator provided by
	 * newSetIterator() or newComplIterator().
	 *
	 * \param i the specified value (which is not
	 * required to be a key in the universe)
	 *
	 * \return the smallest key in the set which is greater than or equal to the specified value, if there is one, or an arbitrary value otherwise
	 */
	virtual long nextOf(long i);

	/*!
	 * \brief Verify if a element of the universe is in the set.
	 *
	 * Verify if the specified element belong or not to the set.
	 *
	 * The parameter i must be a element of the universe, otherwise a error will occur.
	 *
	 * \param i the specified element
	 *
	 * \return true if i belongs to the set and false otherwise
	 */
	virtual bool isInSet(long i) const = 0;

	/*!
	 * \brief Create a vector of the elements in the set
	 *
	 * Creates a vector with the size of the set in which each position
	 * is a element of the set represented by the object.
	 *
	 * The elements are stored respecting the total order between than, so
	 * if \c vec is the vector returned by this method, if \c i \c < \c j then
	 * \c vec[i\c ] is smaller than \c vec[j\c ].
	 *
	 * The parameter size will be overwrite to store the size of the set, so
	 * its previous value will be lost.
	 *
	 * \param size a pointer to store the size of the set.
	 *
	 * \return a array contains all the elements of the set.
	 */
	virtual char * toArray(long* size) = 0;

	/*!
	 * \brief The size of the universe
	 *
	 * This method will return the size of the universe in which this set is embedded.
	 *
	 * \return the size of the universe
	 */
	virtual long universeSize() const;

	/*!
	 * \brief Checks whether this set is empty
	 *
	 * Tests if the set was no elements. If the set was no elements it is empty
	 * and this method should return true.
	 *
	 * As this method depends on the data structure and the universe used, it has to be
	 * implemented in each child concrete class.
	 *
	 * \return \c true if the set is empty and \c false otherwise.
	 */
	virtual bool isEmpty() const = 0;

	/*!
	 * \brief Subset containing the elements between the specified values.
	 *
	 * The elements in the subset are redefined such that an element \c i in this set is mapped to \f$i - 2^{\lfloor \log from \rfloor}\f$
	 *
	 * The returned set is backed by this one.
	 *
	 * \param from first element to appear in the subset
	 * \param to one plus the last element to appear in the subset
	 *
	 * \return the subset of this set
	 */
	virtual DirectlyAddressedSet * subset(long from, long to) const = 0;

	/*!
	 * \brief The complement of the current set, stored in the set res
	 *
	 * This method has the same setComplement(), but do not overwrite the object.
	 *
	 * \param res the object to store the complement of the current set
	 * \see setComplement()
	 */
	virtual void getComplement(DirectlyAddressedSet * res) = 0;

	/*!
	 * \brief Adds the specified key to the set (optional operation).
	 *
	 * The specified key must be a member of the universe, otherwise a error will occur.
	 * This method is not implemented for static sets.
	 *
	 * \param i the specified key.
	 *
	 */
	virtual void toSet(long i) = 0;

	/*!
	 * \brief Removes the specified key from the set (optional operation).
	 *
	 * The specified key must be a member of the universe, otherwise a error will occur.
	 * This method is not implemented for static sets.
	 *
	 * \param i the specified key.
	 *
	 */
	virtual void toCompl(long i) = 0;

	/*!
	 * \brief Swap a element between the set and the complement (optional operation).
	 *
	 * If the specified element is in the set it will be removed, if not
	 * it will be added.
	 * This method is not implemented for static sets.
	 *
	 * The parameter i must be a element of the universe, otherwise a error will occur.
	 *
	 * \param i the especified element.
	 *
	 */
	virtual void flip(long i) = 0;

	/*!
	 * \brief Add all the elements in the universe to the set (optional operation)
	 *
	 * Add all the elements in the universe to the set represented by this object
	 */
	virtual void allToSet() = 0;

	/*!
	 * \brief Add all the elements in the universe to the complement (optional operation)
	 *
	 * Add all the elements in the universe to the complement of the set represented by this object
	 */
	virtual void allToCompl() = 0;

	/*!
	 * \brief The complement of the current set (optional operation)
	 *
	 * Overwrite this object with its complement set.
	 *
	 * More precisely, be A is a set, then \f$\bar{A}\f$ is the complement of A if \f$x \in \bar{A}\f$
	 * if and only if \f$ x \notin A\f$.
	 *
	 */
	virtual void flipAll() = 0;

	/*!
	 * \brief Union of the current set and a specified set (optional operation).
	 *
	 * When this method returns, this object contains all elements of the resulting set.
	 *
	 * \param v the other set to be operated
	 */
	virtual void addAll(DirectlyAddressedSet * v);

	/*!
	 * \brief Symmetric difference of the current set and a specified set (optional operation)
	 *
	 * When this method returns, this object contains all elements of the resulting set.
	 *
	 * \param v the other set to be operated
	 */
	virtual void symDiff(DirectlyAddressedSet * v);

	/*!
	 * \brief Difference of the current set and a specified set (optional operation)
	 *
	 * When this method returns, this object contains all elements of the resulting set.
	 *
	 * \param v the other set to be operated
	 */
	virtual void removeAll(DirectlyAddressedSet * v);

	/*!
	 * \brief Intersection of the current set and a specified set (optional operation)
	 *
	 * When this method returns, this object contains all elements of the resulting set.
	 *
	 * \param v the other set to be operated
	 */
	virtual void retainAll(DirectlyAddressedSet * v);

	/*!
	 * \brief Adds to this set all the elements in the union of two specified sets (optional operation)
	 *
	 * When this method returns, this object contains all elements of the resulting set.
	 *
	 * \param v one set to be operated
	 * \param w the other set
	 *
	 * \see addAll()
	 */
	virtual void unionOf(DirectlyAddressedSet * v, DirectlyAddressedSet * w);

	/*!
	 * \brief Adds to this set all the elements in the symmetric difference of two specified sets (optional operation)
	 *
	 * When this method returns, this object contains all elements of the resulting set.
	 *
	 * \param v one set to be operated
	 * \param w the other set
	 *
	 * \see symDiff()
	 */
	virtual void symDiffOf(DirectlyAddressedSet * v, DirectlyAddressedSet * w);

	/*!
	 * \brief Adds to this set all the elements in the intersection of two specified sets (optional operation)
	 *
	 * When this method returns, this object contains all elements of the resulting set.
	 *
	 * \param v one set to be operated
	 * \param w the other set
	 *
	 * \see retainAll()
	 */
	virtual void intersectOf(DirectlyAddressedSet * v, DirectlyAddressedSet * w);

	/*!
	 * \brief Adds to this set all the elements in the difference of two specified sets (optional operation)
	 *
	 * When this method returns, this object contains all elements of the resulting set.
	 *
	 * \param v one set to be operated
	 * \param w the other set
	 *
	 * \see removeAll()
	 */
	virtual void diffOf(DirectlyAddressedSet * v, DirectlyAddressedSet * w);

	/*!
	 * \brief Determine the first element of the set represented by the current object.
	 *
	 * Determine the first element of the set represented by the current object, according by the
	 * total order implemented by the element.
	 *
	 * If the set is empty the return will depend on the implementation on the concrete subclass.
	 *
	 * \return the first element in the set according to the total order.
	 */
	virtual long firstInSet();

	/*!
	 * \brief Determine the first element of the complement of the set represented by the current object.
	 *
	 * Determine the first element of the complement of the set represented by the current object, according by the
	 * total order implemented by the element.
	 *
	 * If the set is the whole universe the return will depend on the implementation on the concrete subclass.
	 *
	 * \return the first element in the set according to the total order.
	 */
	virtual long firstInCompl() = 0;

	/*!
	 * \brief The cardinality of the set represented by the object.
	 *
	 * The cardinality of the set represented by the set. The cardinality of the set is a
	 * natural number that counts the number of elements in it.
	 *
	 * This method takes linear time in the number of elements in the set.
	 *
	 * \return the size of the current set.
	 */
	virtual long cardOfSet() const;

	/*!
	 * \brief The cardinality of the complement of the set represented by the object.
	 *
	 * The cardinality of the set represented by the set. The cardinality of the set is a
	 * natural number that counts the number of elements in it.
	 *
	 * This method takes linear time in the number of elements in the set.
	 *
	 * \return the size of the complement of the current set.
	 */
	virtual long cardOfCompl() const;

};

char * DirectlyAddressedSet::bitvector = NULL;
int DirectlyAddressedSet::nbv = 0;

inline DirectlyAddressedSet::DirectlyAddressedSet(long size) : u(size), setIt(newIterator()), complIt(newComplIterator()) {

}

inline DirectlyAddressedSet::~DirectlyAddressedSet() {
	delete setIt;
	delete complIt;
}

inline void DirectlyAddressedSet::Iterator::restart() {
	restartFrom(0);
}

inline long DirectlyAddressedSet::nextOf(long i) {
	setIt->restartFrom(i);
	return setIt->next();
}


inline long DirectlyAddressedSet::universeSize() const {
	return u;
}

inline bool DirectlyAddressedSet::isEmpty() const {
	return cardOfSet() == 0;
}

inline void DirectlyAddressedSet::addAll(DirectlyAddressedSet * v) {
	Iterator* it = v->newIterator();
	long i = it->next();
	while (i < v->universeSize()) {
		toSet(i);
		i = it->next();
	}
	delete it;
}


inline void DirectlyAddressedSet::symDiff(DirectlyAddressedSet * v) {
	Iterator* it = v->newIterator();
	long i = it->next();
	while (i < v->universeSize()) {
		flip(i);
		i = it->next();
	}
	delete it;
}


inline void DirectlyAddressedSet::retainAll(DirectlyAddressedSet * v) {
	setIt->restart();
	long i = setIt->next();
	while (i < universeSize()) {
		if (!v->isInSet(i)) {
			toCompl(i);
			setIt->restartFrom(i);
		}
		i = setIt->next();
	}
}

inline void DirectlyAddressedSet::removeAll(DirectlyAddressedSet * v) {
	Iterator* it = v->newIterator();
	long i = it->next();
	while (i < universeSize()) {
		toCompl(i);
		i = it->next();
	}
}


inline void DirectlyAddressedSet::unionOf(DirectlyAddressedSet * v, DirectlyAddressedSet * w) {
	addAll(v);
	addAll(w);
}


inline void DirectlyAddressedSet::symDiffOf(DirectlyAddressedSet * v, DirectlyAddressedSet * w) {
	addAll(v);
	symDiff(w);
}


inline void DirectlyAddressedSet::intersectOf(DirectlyAddressedSet * v, DirectlyAddressedSet * w) {
	Iterator* it = v->newIterator();
	long i = it->next();
	while (i < v->universeSize()) {
		if (w->isInSet(i)) {
			toSet(i);
			it->restartFrom(i);
		}
		i = it->next();
	}
	delete it;
}


inline void DirectlyAddressedSet::diffOf(DirectlyAddressedSet * v, DirectlyAddressedSet * w) {
	Iterator* it = v->newIterator();
	long i = it->next();
	while (i < v->universeSize()) {
		if (!w->isInSet(i)) {
			toSet(i);
			it->restartFrom(i);
		}
		i = it->next();
	}
	delete it;
}


inline void DirectlyAddressedSet::getComplement(DirectlyAddressedSet * res) {
	for(long i = 0; i < u; i++){
		if (isInSet(i))
			res->toCompl(i);
		else
			res->toSet(i);
	}
}

inline long DirectlyAddressedSet::firstInSet() {
	setIt->restart();
	return setIt->next();
}

inline long DirectlyAddressedSet::firstInCompl() {
	complIt->restart();
	return complIt->next();
}

inline long DirectlyAddressedSet::cardOfSet() const {
	setIt->restart();
	long i = setIt->next();
	long count = 0;
	while (i < universeSize()) {
		count++;
		i = setIt->next();
	}

	return count;
}

inline long DirectlyAddressedSet::cardOfCompl() const {
	return universeSize() - cardOfSet();
}

class DirectlyAddressedSetFactory : public Factory<DirectlyAddressedSet> {
public:
	virtual ~DirectlyAddressedSetFactory() {};

	virtual DirectlyAddressedSet * newInstance(long n) = 0;
	virtual DirectlyAddressedSet * newInstance(long n, void * handle) = 0;
};

#endif /* DRIECTLYADDRESSEDSET_H_ */
